public class QuickSort {
	private static int[] array;

	public static void sort(int[] arr) {
		array = arr;
		int startInd = 0;
		int endInd = arr.length - 1;
		doSort(startInd, endInd);
	}

	private static void doSort(int start, int end) {
	        if (start >= end)
	            return;
	        int i = start, j = end;
	        int cur = i - (i - j) / 2;
	        while (i < j) {
	            while (i < cur && (array[i] <= array[cur])) {
	                i++;
	            }
	            while (j > cur && (array[cur] <= array[j])) {
	                j--;
	            }
	            if (i < j) {
	                int temp = array[i];
	                array[i] = array[j];
	                array[j] = temp;
	                if (i == cur)
	                    cur = j;
	                else if (j == cur)
	                    cur = i;
	            }
	        }
	        doSort(start, cur);
	        doSort(cur+1, end);
	    }
}
